/* 
 * File:   Solver.cpp
 * Author: gizmo
 * 
 * Created on September 26, 2010, 2:26 PM
 */

#include "Solver.h"

/**
 * Empty
 */
Solver::Solver() {
}

/**
 * Empty
 * @param orig
 */
Solver::Solver(const Solver& orig) {
}

/**
 * Using graph's max cut weight information a temporary best solution is filled
 * @param gGraph
 */
void Solver::init(Graph* gGraph) {
    graph = gGraph;
    bestSolution.init(graph); // prepare initial best solution // TODO might be probably optimized
    bestSolution[graph->getMaxCutWeightNode()] = 1;
    bestSolution.countCost();
}

/**
 * Empty
 */
Solver::~Solver() {
}

void Solver::startClock() {start = clock();}
void Solver::endClock() {end = clock();}
float Solver::getRunningTime() const {return ((float)end - (float)(start))/CLOCKS_PER_SEC;}

/**
 * Core method of whole problem solving. All magic happens here.
 * Firstly, basic states including one node are created and pushed in stack.
 * Then a loop checking emptiness of the stack is launched.
 * In every iteration, a state is compared to best solution and then is
 * expanded using nextNode field.
 */
void Solver::solve() {
    // fill stack with basic states
    unsigned int i;
    unsigned int nc = graph->getNodeCount();

    startClock();

    for (i = 0; i < nc-1; i++) { // nc -1 for optimization reasons, only half of states (1100 == 0011) is then generated
        State st;
        st.init(graph);
        st[i] = true;
        st.setNextNode(i + 1);
        st.countCost();
        myStack.push(st);
    }


    while (!myStack.empty()) { // we have some states
        State current = myStack.top();
        myStack.pop();
//        cout << current;

        if (current.getCost() > 0 && current.getCost() <= bestSolution.getCost()) {
            bestSolution = current;
        }

        // expand to all possible states
        for (i = current.getNextNode(); i < nc; i++) {
            if (i+1 == nc) continue;
            State st = State(current);
            st[i] = true;
            st.setNextNode(i + 1);
            st.countCost();
            //if (st.getCost() < graph->getMaxCutWeight()) myStack.push(st); // cannot use this, cost may improve by adding some nodes!
            
            myStack.push(st);
        }
    }
    
    endClock();
    
    cout << "Approximate running time: " << getRunningTime() << endl;
}

/**
 *
 * @return best Solution
 */
State & Solver::getBestSolution() {
    return bestSolution;
}

